package com.hy.day;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:1673. 找出最具竞争力的子序列
 * <p>
 * 给你一个整数数组nums和一个正整数 k ，返回长度为k且最具竞争力的nums子序列。
 * 数组的子序列是从数组中删除一些元素（可能不删除元素）得到的序列。
 * 在子序列a和子序列b第一个不相同的位置上，如果a中的数字小于b中对应的数字，那么我们称子序列a比子序列
 * b（相同长度下）更具 竞争力 。 例如，[1,3,4] 比 [1,3,5] 更具竞争力，在第一个不相同的位置，也就是最后一个位置上，4小于5。
 * User:Mr.Du
 * Date:2024/5/24
 * Time:10:53
 */
public class MostCompetitive {

    /**
     * 从数组中找出长度为 k 的最竞争力子序列
     *
     * @param nums 原始数组
     * @param k 要找出的子序列的长度
     * @return 返回长度为 k 的最竞争力子序列
     */
    public int[] mostCompetitive(int[] nums, int k) {
        int n = nums.length; // 数组长度
        int[] st = new int[k]; // 用于存储最竞争力子序列的栈
        int m = 0; // 栈的大小

        // 遍历原始数组
        for (int i = 0; i < n; i++) {
            int x = nums[i];

            // 当栈不为空且当前元素小于栈顶元素且从当前元素到数组末尾的元素个数大于 k 时，出栈操作确保栈保持最竞争力
            while (m > 0 && x < st[m - 1] && m + n - i > k) {
                m--;
            }

            // 如果栈的大小小于 k，则将当前元素入栈
            if (m < k) {
                st[m++] = x;
            }
        }

        return st; // 返回最竞争力子序列
    }
}
